// https://leetcode.cn/problems/reverse-linked-list/description/

// 算法思路总结：
// 1. 递归反转单链表
// 2. 基准情况：空链表或单节点链表直接返回
// 3. 递归反转后续链表，得到新的头节点
// 4. 将当前节点连接到反转后链表的末尾
// 5. 断开当前节点的原始连接，避免成环
// 6. 时间复杂度：O(n)，空间复杂度：O(n)（递归栈）

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode* createLinkedList(const vector<int>& nums)
{
    if (nums.empty()) return nullptr;
    
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    
    for (int num : nums)
    {
        cur->next = new ListNode(num);
        cur = cur->next;
    }
    
    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

void printLinkedList(ListNode* head)
{
    if (!head)
    {
        cout << "空链表" << endl;
        return;
    }
    
    ListNode* cur = head;
    while (cur)
    {
        cout << cur->val;
        if (cur->next)
            cout << " -> ";
        else
            cout << " -> nullptr";
        cur = cur->next;
    }
    cout << endl;
}

class Solution 
{
public:
    ListNode* reverseList(ListNode* head) 
    {
        if (head == nullptr || head->next == nullptr)
            return head;

        auto newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

int main()
{
    vector<int> v1 = {1,2,3,4,5}, v2 = {1,2}, v3 = {};
    Solution sol;

    auto l1 = createLinkedList(v1);
    auto l2 = createLinkedList(v2);
    auto l3 = createLinkedList(v3);

    auto r1 = sol.reverseList(l1);
    auto r2 = sol.reverseList(l2);
    auto r3 = sol.reverseList(l3);

    printLinkedList(r1);
    printLinkedList(r2);
    printLinkedList(r3);

    return 0;
}